package com.thghh.ch5.bst;

import com.thghh.ch5.huffman.Traverse;
import com.thghh.ch5.huffman.TraverseFactory;

import java.util.*;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;

/**
 * {@see https://www.cnblogs.com/songdechiu/p/6821168.html}
 * {@see https://www.cnblogs.com/LiaHon/p/11203229.html}
 * {@see https://www.cnblogs.com/LiaHon/p/11221634.html}
 *
 * @author Zhikang.Peng
 * @version 1.0
 * @email thghh@qq.com
 * @date 2020/10/13 14:28  v
 */
public class BinarySortTree<K extends Comparable<K>, V> extends AbstractMap<K, V> {

    private transient Node<K, V> root;
    private transient int size;
    private transient int modCount = 0;
    private transient NodeSet nodeSet;

    public BinarySortTree() {
    }

    /**
     * Inserts the specified key-value pair into the symbol table, overwriting the old
     * value with the new value if the symbol table already contains the specified key.
     * Deletes the specified key (and its associated value) from this symbol table
     * if the specified value is {@code null}.
     *
     * @param key   the key
     * @param value the value
     * @throws NullPointerException if {@code key} is {@code null}
     */
    public V put(K key, V value) {
        Node<K, V> t = root;
        // 根节点加入
        if (t == null) {
            key.compareTo(key);
            root = new Node<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        if (key == null)
            throw new NullPointerException("key is null.");
        int cmp;
        Node<K, V> parent;
        do {
            parent = t;
            cmp = key.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
        Node<K, V> n = new Node<>(key, value, parent);
        if (cmp < 0)
            parent.left = n;
        else
            parent.right = n;
        fixAfterInsertion(n);
        size++;
        modCount++;
        return null;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        NodeSet ns = nodeSet;
        return (ns != null) ? ns : (nodeSet = new NodeSet());
    }

    @Override
    public void forEach(BiConsumer<? super K, ? super V> action) {
        Objects.requireNonNull(action);
        int expectedModCount = modCount;
        for (Node<K, V> n = getFirstNode(); n != null; n = successor(n)) {
            action.accept(n.key, n.value);
            if (expectedModCount != modCount) {
                throw new ConcurrentModificationException();
            }
        }
    }

    @Override
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        Objects.requireNonNull(function);
        int expectedModCount = modCount;
        for (Node<K, V> n = getFirstNode(); n != null; n = successor(n)) {
            n.value = function.apply(n.key, n.value);
            if (expectedModCount != modCount) {
                throw new ConcurrentModificationException();
            }
        }
    }

    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        Node<K, V> p = getNode(key);
        if (p != null && Objects.equals(oldValue, p.value)) {
            p.value = newValue;
            return true;
        }
        return false;
    }

    @Override
    public V replace(K key, V value) {
        Node<K, V> p = getNode(key);
        if (p != null) {
            V oldValue = p.value;
            p.value = value;
            return oldValue;
        }
        return null;
    }

    /**
     * Balancing operations.
     * <p>
     * Implementations of rebalancings during insertion and deletion are
     * slightly different than the CLR version.  Rather than using dummy
     * nilnodes, we use a set of accessors that deal properly with null.  They
     * are used to avoid messiness surrounding nullness checks in the main
     * algorithms.
     */

    private static <K, V> boolean colorOf(Node<K, V> p) {
        return (p == null ? BLACK : p.color);
    }

    private static <K, V> Node<K, V> parentOf(Node<K, V> p) {
        return (p == null ? null : p.parent);
    }

    private static <K, V> void setColor(Node<K, V> p, boolean c) {
        if (p != null) p.color = c;
    }

    private static <K, V> Node<K, V> leftOf(Node<K, V> p) {
        return (p == null) ? null : p.left;
    }

    private static <K, V> Node<K, V> rightOf(Node<K, V> p) {
        return (p == null) ? null : p.right;
    }

    /**
     * 逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点
     * <pre>
     *             PL               PL                  P                P
     *            /  \            / | X               / X \             / \
     *           C1   P   --->   C1 |  P     --->   PL  X  PR  --->    PL  PR
     *               / \            | / \          /  \ X             /  \
     *              C2  PR          C2  PR        C1   c2            C1  c2
     * </pre>
     *
     * @param p
     */
    private void rotateLeft(Node<K, V> p) {
        if (p != null) {
            Node<K, V> r = p.right;
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent;
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
                p.parent.left = r;
            else
                p.parent.right = r;
            r.left = p;
            p.parent = r;
        }
    }

    /**
     * 顺时针旋转两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点
     * <pre>
     *              P                  P                PL               PL
     *             / \               X | \            / X \            /  \
     *            PL  PR   --->    PL  |  PR  --->   C1 X  P   --->   C1   P
     *           /  \             /  \ |                X / \             / \
     *          C1  c2           C1   c2                C2  PR           C2  PR
     * </pre>
     *
     * @param p
     */
    private void rotateRight(Node<K, V> p) {
        if (p != null) {
            Node<K, V> l = p.left;
            p.left = l.right;
            if (l.right != null)
                l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else
                p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }

    /**
     * <pre>
     * 规则:
     *  1.节点分为红色或者黑色
     *  2.根节点必为黑色
     *  3.叶子节点都为黑色,且为null
     *  4.连接红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点)
     *  5.从任意节点出发,到其每个叶子节点的路径中包含相同数量的黑色节点
     *  6.新加入到红黑树的节点为红色节点
     *
     *  自平衡，变色和旋转:
     *                     无需调整	       |           [变色]即可实现平衡	      |  [旋转+变色]才可实现平衡
     * 情况1:	当父节点为黑色时插入子节点 | 空树插入根节点,将根节点红色变为黑色  |	父节点为红色左节点,叔父节点为黑色,插入左子节点,那么通过[左左节点旋转]
     * 情况2:	-	                       | 父节点和叔父节点都为红色             | 父节点为红色左节点,叔父节点为黑色,插入右子节点,那么通过[左右节点旋转]
     * 情况3:	-		                   |               -                      | 父节点为红色右节点,叔父节点为黑色,插入左子节点,那么通过[右左节点旋转]
     * 情况4:	-		                   |               -                      | 父节点为红色右节点,叔父节点为黑色,插入右子节点,那么通过[右右节点旋转]
     * </pre>
     *
     * @param x
     */
    private void fixAfterInsertion(Node<K, V> x) {
        // 新加入到红黑树的节点为红色节点
        x.color = RED;

        // 父节点为黑色时，无需进行树结构调整，只有当父节点为红色时，才需要调整
        while (x != null && x != root && x.parent.color == RED) {
            // 如果父节点是左节点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                // 叔父节点
                Node<K, V> y = rightOf(parentOf(parentOf(x)));
                // 如果叔父节点是红色，对应[父节点和叔父节点都为红色]，通过变色即可实现平衡
                if (colorOf(y) == RED) {
                    // 父节点和叔父节点设置为黑色，祖父节点设置为红色
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else { // 叔父节点为黑色
                    // 父节点为红色左节点，叔父节点为黑色，插入右子节点，那么通过【左右节点旋转】
                    // 通过[左右节点旋转],先父节点[左旋]，然后祖父节点[右旋]，搭配[变色]
                    if (x == rightOf(parentOf(x))) {
                        // 在x左旋后，x和它的右节点关系互换了
                        x = parentOf(x);
                        // 先父节点[左旋]
                        rotateLeft(x);
                    }
                    //设置父节点和祖父节点颜色
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    // 然后祖父节点[右旋]
                    rotateRight(parentOf(parentOf(x)));
                }
            } else { // 父节点为右节点
                // 获取叔父节点
                Node<K, V> y = leftOf(parentOf(parentOf(x)));
                // 父节点和叔父节点都为红色, 此时通过变色即可实现平衡
                if (colorOf(y) == RED) {
                    // 父节点和叔父节点设置为黑色，祖父节点设置为红色
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    // 父节点为红色右节点,叔父节点为黑色,插入左子节点,那么通过[右左节点旋转]
                    // 先父节点[右旋]，然后祖父节点[左旋]，搭配[变色]
                    if (x == leftOf(parentOf(x))) {
                        // 这里为什么要把父节点赋予x，在x右旋之后，x和它的左节点关系互换了
                        x = parentOf(x);
                        // 先父节点[右旋]
                        rotateRight(x);
                    }
                    // 变色
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    // 然后祖父节点[左旋]
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        // 根节点颜色必须是黑色
        root.color = BLACK;
    }

    /**
     * Returns the value associated with the given key.
     *
     * @param key the key
     * @return the value associated with the given key if the key is in the symbol table
     * and {@code null} if the key is not in the symbol table
     * @throws NullPointerException if {@code key} is {@code null}
     */
    public V get(K key) {
        Node<K, V> p = getNode(key);
        return (p == null ? null : p.value);
    }

    /**
     * Returns this map's entry for the given key, or {@code null} if the map
     * does not contain an entry for the key.
     *
     * @return this map's entry for the given key, or {@code null} if the map
     * does not contain an entry for the key
     * @throws NullPointerException if the specified key is null
     *                              and this map uses natural ordering, or its comparator
     *                              does not permit null keys
     */
    private Node<K, V> getNode(K key) {
        if (key == null)
            throw new NullPointerException("key is null.");
        Node<K, V> p = root;
        while (p != null) {
            int cmp = key.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

    /**
     * Returns the first Entry in the TreeMap (according to the TreeMap's
     * key-sort function).  Returns null if the TreeMap is empty.
     */
    final Node<K, V> getFirstNode() {
        Node<K, V> p = root;
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }

    /**
     * Returns the last Entry in the TreeMap (according to the TreeMap's
     * key-sort function).  Returns null if the TreeMap is empty.
     */
    final Node<K, V> getLastNode() {
        Node<K, V> p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
    }

    /**
     * Gets the entry corresponding to the specified key; if no such entry
     * exists, returns the entry for the least key greater than the specified
     *
     * @param key if no such entry exists, returns {@code null}.
     */
    final Node<K, V> getCeilingNode(K key) {
        Node<K, V> p = root;
        while (p != null) {
            int cmp = key.compareTo(p.key);
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else if (cmp > 0) {
                if (p.right != null) {
                    p = p.right;
                } else {
                    Node<K, V> parent = p.parent;
                    Node<K, V> ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else return p;
        }
        return null;
    }

    /**
     * Gets the entry corresponding to the specified key; if no such entry
     * exists, returns the entry for the greatest key less than the specified
     *
     * @param key if no such entry exists, returns {@code null}.
     */
    final Node<K, V> getFloorNode(K key) {
        /* A、如果根节点是null，则直接返回null。
         * B、如果根节点键值大于key，则继续floor(key)在左子树中，所以继续在左子树中查找。
         * C、如果根节点键值刚好等于key，则根节点的键值即为floor(key)，直接返回该键。
         * D、如果根节点键值小于key，那么根节点的key有可能就是floor(key)，只要右子树中不存在节点的key小于等于输入的key。
         * E、重复ABCD
         * */
        Node<K, V> p = root;
        while (p != null) {
            int cmp = key.compareTo(p.key);
            if (cmp > 0) {
                if (p.right != null)
                    p = p.right;
                else
                    return p;
            } else if (cmp < 0) {
                if (p.left != null) {
                    p = p.left;
                } else {
                    Node<K, V> parent = p.parent;
                    Node<K, V> ch = p;
                    while (parent != null && ch == parent.left) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else return p;
        }
        return null;
    }

    public V remove(K key) {
        Node<K, V> p = getNode(key);
        if (p == null) {
            return null;
        }
        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
    }

    private void fixAfterDeletion(Node<K, V> x) {
        // x不是root并且是黑色节点
        while (x != root && colorOf(x) == BLACK) {
            // x是左节点
            if (x == leftOf(parentOf(x))) {
                // x的兄弟节点
                Node<K, V> sib = rightOf(parentOf(x));

                /**
                 * 场景1：当x是左黑色节点，兄弟节点sib是红色节点
                 * 兄弟节点由红转黑，父节点由黑转红，按父节点左旋，
                 * 左旋后树的结构变化了，这时重新赋值sib，将sib指向了x的兄弟节点
                 * <pre>
                 *        p(B)               p(R)               sib(B)            pi(B)
                 *       /  \        1      /  \        2       /  \       3      /  \
                 *     x(B) sib(R)  -->   x(B) sib(B)  -->    p(R) r2(B)  -->   p(R) r2(B)
                 *         / \                 / \            /  \              /  \
                 *      r1(B) r2(B)        r1(B) r2(B)      x(B) r1(B)        x(B) sib(B)
                 *
                 * </pre>
                 */
                if (colorOf(sib) == RED) {
                    // 保证了场景4中sib为黑色节点
                    setColor(sib, BLACK);  // 1
                    setColor(parentOf(x), RED); // 1
                    rotateLeft(parentOf(x)); // 2
                    sib = rightOf(parentOf(x)); // 3
                }
                /**
                 * 场景2：节点x、x的兄弟节点sib、sib的左子节点和右子节点都为黑色时，
                 * 需要将该节点sib由黑变红，同时将x指向当前x的父节点并颜色变成黑色
                 * <pre>
                 *         pi(B)            pi(B)             pi(B)             pi(B)
                 *         /  \      1      /  \       2      /  \     最后     /  \
                 *       p(R) r2(B) -->   p(R) r2(B)  -->   x(R) r2(B)  -->   x(B) r2(B)
                 *       /  \             /  \              /  \              /  \
                 *     x(B) sib(B)      x(B) sib(R)       xl(B) sib(R)      xl(B) sib(R)
                 *          / \              / \                / \               / \
                 *      b1(B) b2(B)      b1(B) b2(B)        b1(B) b2(B)       b1(B) b2(B)
                 * </pre>
                 */
                if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED); // 1
                    x = parentOf(x); // 2
                } else {
                    /**
                     * 场景3：节点x、x的兄弟节点sib、sib的右子节点都为黑色，sib的左子节点为红色时，
                     * 需要将sib左子节点设置为黑色，sib节点设置为红色，同时按sib右旋，再将sib指向x的
                     * 兄弟节点
                     * <pre>
                     *       p(B)             p(B)             p(B)              p(B)
                     *       /  \        1    /  \        2    /  \        3     /  \
                     *     x(B) sib(B)  --> x(B) sib(R)  --> x(B) r1(B)   -->  x(B) sib(B)
                     *          / \              / \                \                 \
                     *      r1(R) r2(B)      r1(B) r2(B)            sib(R)            bl(R)
                     *                                                \                 \
                     *                                                 r2(B)             r2(B)
                     * </pre>
                     */
                    if (colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK); // 1
                        setColor(sib, RED);
                        rotateRight(sib); // 2
                        sib = rightOf(parentOf(x)); // 3
                    }

                    /**
                     * 场景4：节点x、x的兄弟节点sib都为黑色，而sib的左右子节点都为红色或者右子节点为红色、
                     * 左子节点为黑色，此时需要将sib节点的颜色设置成和x的父节点p相同的颜色，
                     * 设置x的父节点为黑色，设置sib右子节点为黑色，左旋x的父节点p，然后将x赋值为root
                     * <pre>
                     *         p(B)              p(B)                sib(B)             sib(B)
                     *        /  \              /  \                /  \               /  \
                     *     x(B) sib(B)   --> x(B) sib(B)   -->    p(B) b2(B)  -->    p(B) b2(B)
                     *          /  \              /  \            /  \               /  \
                     *       b1(?) b2(R)      b1(?) b2(B)      x(B) b1(?)         x1(B) b1(?)
                     * </pre>
                     */
                    setColor(sib, colorOf(parentOf(x))); // 1
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x)); // 2
                    x = root; // 3
                }
            } else { // x是右节点的情况下
                Node<K, V> sib = leftOf(parentOf(x));
                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
                }

                if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(x));
                    }

                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));
                    x = root;
                }
            }
        }
        // 最后把x的颜色设置为黑色
        setColor(x, BLACK);
    }

    /**
     * Delete node p, and then rebalance the tree.
     * 在删除节点的时候我们只需考虑一下三种情况
     * <pre>
     * 1.要删除的节点是叶子结点，直接把叶子节点删除即可
     *           7
     *          / \
     *         /   \
     *        3    10
     *       / \   / \
     *      1  5  9  12
     *
     * 2.要删除的节点有左节点但是没有右节点，或者有右节点但是没有左节点
     *   直接把要删除节点的左节点或右节点替换要删除的节点
     *           7      |        7
     *          / \     |       / \
     *         /   \    |      /   \
     *        3    10   |     3    10
     *       /    /     |      \     \
     *      1    9      |       5     12
     *
     * 3.要删除的节点既有左节点又有右节点，在这种情况下，
     *   我们只需要将找到待删节点的右子树中值最小的节点（后继），
     *   将其删除并且获取其值，并用其值替换待删节点的值即可
     *           7
     *          / \
     *         /   \
     *        3    10
     *       / \   / \
     *      1  5  9  12
     *  </pre>
     */
    private void deleteEntry(Node<K, V> p) {
        modCount++;
        size--;

        if (p.left != null && p.right != null) { // p has 2 children
            Node<K, V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        }
        // Start fixup at replacement node, if it exists.
        Node<K, V> replacement = (p.left != null ? p.left : p.right);
        if (replacement != null) { // p has left or right children
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left = replacement;
            else
                p.parent.right = replacement;
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { // No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);
            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

    /**
     * Returns the successor of the specified Entry, or null if no such.
     * https://blog.csdn.net/iwts_24/article/details/87165743
     * <pre>
     * 1.当前节点左子树不为空的情况下，找右子树最小的节点（从上往下找）
     * 2.当前节点右子树为空的情况下，就是该结点没有右子树但是有比该结点大的祖先结点(从下往上找)
     *   比如当前节点为3，找到的后继节点为5
     *   比如当前节点为7，找到的后继节点为5
     *  	    5
     *        /  \
     *       1	  6
     *        \    \
     *         3    7
     *        /
     *       2
     *     1 2 3 5 6 7   将上面树结构，平面展示的数组结构
     * </pre>
     */
    static <K, V> Node<K, V> successor(Node<K, V> t) {
        if (t == null)
            return null;
        else if (t.right != null) {
            // 右子树中值最小的节点
            Node<K, V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            Node<K, V> p = t.parent;
            Node<K, V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

    /**
     * Returns the predecessor of the specified Entry, or null if no such.
     */
    static <K, V> Node<K, V> predecessor(Node<K, V> t) {
        if (t == null)
            return null;
        else if (t.left != null) {
            // 左子树中值最大的节点
            Node<K, V> p = t.left;
            while (p.right != null)
                p = p.right;
            return p;
        } else {
            Node<K, V> p = t.parent;
            Node<K, V> ch = t;
            while (p != null && ch == p.left) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public void clear() {
        modCount++;
        size = 0;
        root = null;
    }

    public TraverseFactory<V> getTraverseFactory() {
        TraverseNode<K, V> node = new TraverseNode(root);
        return new TraverseFactory<>(node);
    }

    /**
     * Test two values for equality.  Differs from o1.equals(o2) only in
     * that it copes with {@code null} o1 properly.
     */
    static final boolean valEquals(Object o1, Object o2) {
        return (o1 == null ? o2 == null : o1.equals(o2));
    }

    // Red-black mechanics
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    static class Node<K, V> implements Map.Entry<K, V> {
        K key;
        V value;
        Node<K, V> left;
        Node<K, V> right;
        Node<K, V> parent;
        boolean color = BLACK;

        Node(K key, V value, Node<K, V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        /**
         * Returns the key.
         *
         * @return the key
         */
        public K getKey() {
            return key;
        }

        /**
         * Returns the value associated with the key.
         *
         * @return the value associated with the key
         */
        public V getValue() {
            return value;
        }

        /**
         * Replaces the value currently associated with the key with the given
         * value.
         *
         * @return the value associated with the key before this method was
         * called
         */
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Node))
                return false;
            Node<?, ?> e = (Node<?, ?>) o;

            return valEquals(key, e.getKey()) && valEquals(value, e.getValue());
        }

        public int hashCode() {
            int keyHash = (key == null ? 0 : key.hashCode());
            int valueHash = (value == null ? 0 : value.hashCode());
            return keyHash ^ valueHash;
        }

        public String toString() {
            return key + "=" + value;
        }
    }

    class NodeSet extends AbstractSet<Map.Entry<K, V>> {

        @Override
        public Iterator<Entry<K, V>> iterator() {
            return new NodeIterator(getFirstNode());
        }

        @Override
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
            Object value = entry.getValue();
            Node<K, V> p = getNode(entry.getKey());
            return p != null && valEquals(p.getValue(), value);
        }

        @Override
        public boolean remove(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
            Object value = entry.getValue();
            Node<K, V> p = getNode(entry.getKey());
            if (p != null && valEquals(p.getValue(), value)) {
                deleteEntry(p);
                return true;
            }
            return false;
        }

        @Override
        public Spliterator<Entry<K, V>> spliterator() {
            return null;
        }

        @Override
        public void clear() {
            BinarySortTree.this.clear();
        }

        @Override
        public int size() {
            return BinarySortTree.this.size();
        }
    }

    final class NodeIterator extends PrivateNodeIterator<Map.Entry<K, V>> {

        NodeIterator(Node<K, V> first) {
            super(first);
        }

        @Override
        public Entry<K, V> next() {
            return nextNode();
        }
    }

    abstract class PrivateNodeIterator<T> implements Iterator<T> {
        Node<K, V> next;
        Node<K, V> lastReturned;
        int expectedModCount;

        PrivateNodeIterator(Node<K, V> first) {
            expectedModCount = modCount;
            lastReturned = null;
            next = first;
        }

        final Node<K, V> nextNode() {
            Node<K, V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            next = successor(e);
            lastReturned = e;
            return e;
        }

        final Node<K, V> prevNode() {
            Node<K, V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            next = predecessor(e);
            lastReturned = e;
            return e;
        }

        @Override
        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // deleted entries are replaced by their successors
            if (lastReturned.left != null && lastReturned.right != null)
                next = lastReturned;
            deleteEntry(lastReturned);
            expectedModCount = modCount;
            lastReturned = null;
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

    }

    static class TraverseNode<K, V> extends Node<K, V> implements Traverse<V> {

        Node<K, V> node;

        TraverseNode(Node<K, V> node) {
            this(node.key, node.value, node.parent);
            this.left = node.left;
            this.right = node.right;
            this.node = node;
        }

        TraverseNode(K key, V value, Node<K, V> parent) {
            super(key, value, parent);
        }

        @Override
        public Traverse<V> getLeft() {
            if (node.left != null)
                return new TraverseNode(node.left);
            else
                return null;
        }

        @Override
        public Traverse<V> getRight() {
            if (node.right != null)
                return new TraverseNode(node.right);
            else
                return null;
        }

        @Override
        public Traverse<V> getObject() {
            return this;
        }
    }
}
